package com.algorithm.lesson_06;

public class FindFirstIntersectNode {

	/**
	 * 获取以head指针为头结点的链表的第一个入环结点
	 * 
	 * @param head
	 * @return null:无环
	 */

	// 环外长度为L1，环内长度为L2
	// S在环内走了P步
	// S走了L1+P
	// S离第一个入环结点距离为P
	// 当S和F相遇则F走了2(L1+P)=2L1+2P(步)在环内走了L1+2P步
	// F离第一个入环结点的距离为 L1+2P-L2=P-->L1=L2-P
	public static Node getLoopNode(Node head) {

		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}

		Node slow = head.next;// 慢指针，一次走一步
		Node fast = head.next.next;// 快指针，一次走两步

		// 让快指针和慢指针相遇
		while (slow != fast) {
			if (fast.next == null || fast.next.next == null) {
				return null;
			}
			slow = slow.next;
			fast = fast.next.next;
		}

		fast = head;

		// 相遇后让快指针从头出发，一步一步移动相遇的即为第一个入环结点
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}

		return slow;
	}
	
	

}
